package 中等;

public class 最大二叉树 {


    public static void main(String[] args) {
        int[] nums = {3,2,1,6,0,5};
        long start = System.currentTimeMillis();
        System.out.println(constructMaximumBinaryTree1(nums));
        long end = System.currentTimeMillis();
        System.out.println(end-start);

    }

    public static TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        if (len==0){
            return null;
        }
        int max = nums[0];
        int maxIndex = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i]>max){
                max = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(max);
        int[] left = new int[maxIndex];
        int[] right = new int[len-1-maxIndex];
        int index = 0;
        for (int i = 0; i < len; i++) {
            if (i<maxIndex){
                left[index++] = nums[i];
            }else if (i==maxIndex){
                index = 0;
            }else {
                right[index++] = nums[i];
            }
        }
        root.left = constructMaximumBinaryTree(left);
        root.right = constructMaximumBinaryTree(right);

        return root;
    }

    public static TreeNode constructMaximumBinaryTree1(int[] nums) {
        return bulid(nums,0 ,nums.length-1 );
    }

    public static TreeNode bulid(int[] nums,int start,int end){
        if (start > end){
            return null;
        }
        int maxIndex = start;
        int max = nums[start];
        for (int i = start+1; i <= end; i++) {
            if (nums[i]  >max){
                max = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(max);
        root.right = bulid(nums,maxIndex+1 , end);
        root.left = bulid(nums,start ,maxIndex-1 );
        return root;
    }
}
